/*
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]
*/
// 2020.8.14 自己写的，复杂度太高

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string tmp("");
        backtracing(2*n,res,tmp);
        return res;
    }
private:
    void backtracing(int n,vector<string>& res,string& tmp){
        if(tmp.size()==n){
            //cout<<tmp<<" "<<isGood(tmp)<<endl;
            if(isGood(tmp)&&find(res.begin(),res.end(),tmp)==res.end()){
                res.push_back(tmp);
            }
            return;
        }
        for(int i=tmp.size();i<n;i++){
            tmp.push_back('(');
            backtracing(n,res,tmp);
            tmp.pop_back();
            tmp.push_back(')');
            backtracing(n,res,tmp);
            tmp.pop_back();

        }

    }
    bool isGood(string& s){
        stack<char> mystack;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                mystack.push(s[i]);
            }else{
                if(mystack.empty()){
                    return false;
                }
                if(mystack.top()=='('){
                    mystack.pop();
                }else{
                    return false;
                }
            }
        }
        return mystack.empty();
    }
};

// 官方题解答案
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string tmp("");
        backtracing(n,0,0,res,tmp);
        return res;
    }
private:
    void backtracing(int n,int open,int close,vector<string>& res,string& tmp){
        if(tmp.size()==2*n){
            //cout<<tmp<<" "<<isGood(tmp)<<endl;
            res.push_back(tmp);
            return;
        }
        if(open<n){
            tmp.push_back('(');
            backtracing(n,open+1,close,res,tmp);
            tmp.pop_back();
        }
        if(close<open){
            tmp.push_back(')');
            backtracing(n,open,close+1,res,tmp);
            tmp.pop_back();
        }

    }
};